package leetcode.monotoni;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 84. 柱状图中最大的矩形
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * <p>
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * <p>
 * <p>
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 * 示例 2：
 * <p>
 * <p>
 * <p>
 * 输入： heights = [2,4]
 * 输出： 4
 */
public class LargestRectangleArea {

    /**
     * 单调栈
     * 单调递增
     *
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return heights[0];
        }

        int ans = 0;
        int[] arr = new int[len + 2];
        // arr需要比heights大两个单位，作为首尾的边界,值都为0
        for (int i = 1; i < arr.length - 1; i++) {
            arr[i] = heights[i - 1];
        }

        Deque<Integer> stack = new ArrayDeque<>();

        // 从左往右遍历
        for (int i = 0; i < arr.length; i++) {
            // i == 0 时 arr[i] == 0,先put个0进去垫底
            // i == length-1 时 arr[length-1] == 0,肯定可以进入while处理
            while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
                int curHigh = arr[stack.pop()];
                int temp = curHigh * (i - stack.peek() - 1);
                ans = Math.max(temp, ans);
            }
            stack.push(i);
        }

        return ans;
    }
}
